package com.weecee.zs.utils.al;

import java.util.Arrays;
import java.util.List;

/**
 * Copyright ©2016
 *
 * @author shuai.zhang  on 2017/3/20
 * @version 1.0.0
 * @description
 */
public class MaxHeapfy {

	public <T extends Comparable<T>> List<T> build_max_heap(List<T> list) {
		for (int i = list.size() / 2; i >= 0; i--) {
			MaxHeapfy(list, i, list.size());
		}
		return list;
	}


	public <T extends Comparable<T>> void MaxHeapfy(List<T> list, int parentIndex, int size) {

		int leftChildIndex = parentIndex * 2 + 1;
		int rightChildIndex = parentIndex * 2 + 2;
		int maxValueIndex = parentIndex;

		if (leftChildIndex < size && list.get(leftChildIndex).compareTo(list.get(maxValueIndex)) > 0) {
			maxValueIndex = leftChildIndex;
		}

		if (rightChildIndex < size && list.get(rightChildIndex).compareTo(list.get(maxValueIndex)) > 0) {
			maxValueIndex = rightChildIndex;
		}

		if (maxValueIndex != parentIndex) {
			T parentValue = list.get(parentIndex);
			list.set(parentIndex, list.get(maxValueIndex));
			list.set(maxValueIndex, parentValue);
			MaxHeapfy(list, maxValueIndex, size);
		}
	}


	public <T extends Comparable<T>> List<T> Sort(List<T> t) {
		for (int i = t.size() - 1; i > 0; i--) {
			T tmp = t.get(i);
			t.set(i, t.get(0));
			t.set(0, tmp);
			MaxHeapfy(t, 0, i);
		}
		return t;
	}

	public static void main(String[] args) {
		MaxHeapfy maxHeapfy = new MaxHeapfy();
		List<Integer> integers = maxHeapfy.build_max_heap(Arrays.asList(1, 3, 5, 6, 7, 111, 22, 199, 100));
		System.out.println(integers);
		List<Integer> sort = maxHeapfy.Sort(integers);
		System.out.println(sort);
	}
}
